package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/">二叉树的锯齿形层序遍历(Binary Tree Zigzag Level Order Traversal)</a>
 * <p>给你二叉树的根节点 root ，返回其节点值的<b>锯齿形层序遍历</b>。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *                  3
 *                 / \
 *                9   20
 *                    / \
 *                   15  7
 *      输出：[[3],[20,9],[15,7]]
 *
 * 示例 2：
 *      输入：root = [1]
 *      输出：[[1]]
 *
 * 示例 3：
 *      输入：root = []
 *      输出：[]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [0, 2000] 内</li>
 *     <li>-100 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/11 11:05
 */
public class LC0103BinaryTreeZigzagLevelOrderTraversal_M {

    static class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> retList = new ArrayList<>();
            if (root == null) {
                return retList;
            }
            // 进入队列的顺序是否为从左往右
            boolean isFromLeftToRight = true;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                Deque<Integer> currLevelNodeValQueue = new LinkedList<>();
                int currLevelNodeSize = queue.size();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    if (isFromLeftToRight) {
                        currLevelNodeValQueue.add(currNode.val);
                    } else {
                        currLevelNodeValQueue.push(currNode.val);
                    }
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                }
                isFromLeftToRight = !isFromLeftToRight;
                retList.add(new LinkedList<>(currLevelNodeValQueue));
            }
            return retList;
        }

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        Solution solution = new Solution();
        TreeNode.printTreeNodeVal(solution.zigzagLevelOrder(root));
    }
}
